import java.security.KeyStore;
import java.util.*;

public class Solution {
    public static void main(String[] args) {
//        String a = "";
//        char c = 'c';
//        System.out.println(a += c);
        Solution s = new Solution();
        String[] words = new String[]{"wrt", "wrf", "er", "ett", "rftt"};
        String[] words1 = new String[]{"z", "x", "z"};
        System.out.println(s.alienOrder(words));
    }

    public String alienOrder(String[] words) {
        /***
         * 火星词典
         *
         */
        // 1 预处理
        int n = words.length;
        // -建立入度表与映射表
        Map<Character, Integer> inEdges = new HashMap<>();
        for(String e: words) {
            for(char c: e.toCharArray()) {
                inEdges.put(c, 0);
            }
        }
        // -建图
        Map<Character, List<Character>> edges = new HashMap<>();
        for(int i = 0; i < n-1; i++) {
            for(int j = i+1; j < n; j++) {
                char[] front = words[i].toCharArray();
                char[] back = words[j].toCharArray();
                // -比较建图，并记录入度
                boolean flg = true;
                for(int k = 0; k < Math.min(back.length, front.length); k++) {
                    if(front[k] != back[k]) {
                        flg = false;
                        if(!edges.containsKey(front[k])) {
                            edges.put(front[k], new ArrayList<>());
                        }
                        edges.get(front[k]).add(back[k]);
                        inEdges.put(back[k], inEdges.get(back[k]) + 1);
                        // -每个单词之间只需比较一次，只要比较出结果，直接返回！
                        break;
                    }
                }
                // -未被执行，说明全等，判断长度
                if(flg) {
                    if(front.length > back.length) {
                        return "";
                    }
                }
            }
        }

        // 2 BFS执行拓扑排序
        String ret = "";
        // -创建队列，并将入度为0的元素入队
        Queue<Character> queue = new LinkedList<>();
        for(Map.Entry<Character, Integer> e:inEdges.entrySet()) {
            if(e.getValue() == 0) {
                queue.offer(e.getKey());
            }
        }
        while(!queue.isEmpty()) {
            // -1 出队
            char cur = queue.poll();
            ret += cur;
            // -2 消除边和入度
            for(char e: edges.getOrDefault(cur, new ArrayList<>())) {
                inEdges.put(e, inEdges.get(e) - 1);
                // -3 将入度为0的点入队
                if(inEdges.get(e) == 0) {
                    queue.offer(e);
                }
            }
        }

        // 3 判断是否有环，有则返回“”，无则返回ret
        for(int e: inEdges.values()) {
            if(e >= 1) {
                return "";
            }
        }

        // 4 返回值
        return ret;
    }
}
